package leetcode_100;

/**
 *@author 周杨
 *		SearchInsertPosition Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
		
		You may assume no duplicates in the array.
		
		Example 1:
		
		Input: [1,3,5,6], 5
		Output: 2
		Example 2:
		
		Input: [1,3,5,6], 2
		Output: 1
		Example 3:
		
		Input: [1,3,5,6], 7
		Output: 4
		Example 1:
		
		Input: [1,3,5,6], 0
		Output: 0

 *describe:分治查找插入位置 时间复杂度O(logN) AC 100%
 *2018年4月13日 下午1:55:19
 */
public class SearchInsertPosition_35 {

	public static void main(String[] args) {
		int nums1[]=new int[] {1,3,5,6};
		int nums2[]=new int[] {1,3};
		int nums3[]=new int[] {3,5,7,9,10};
		System.out.println(searchInsert(nums3, 8));

	}
	public static int searchInsert(int[] nums, int target) {
		if(nums.length==0)
			return 0;
        return help(nums,0,nums.length-1,target);
    }
	private static int help(int[] nums, int l, int r, int target) {
		if(r<l)
			return r+1;//越界
		if(r==l) {//此处只有一个元素了
			if(nums[l]==target)
				return r;
			else if(nums[l]<target) 
				return l+1;
			
			else
				return l;
		}
		int m=(l+r)/2;
		if(nums[m]==target)
			return m;
		else if(nums[m]<target)
				return help(nums,m+1,r,target);
		else
			return help(nums,l,m-1,target);
		}
	
}
